/*
 * simplehash.h
 *
 *	  当包含此文件时，该文件生成一个“模板化”的（通过宏）
 *	  开放地址哈希表实现，专门针对用户定义的类型。
 *
 *	  对于不敏感于性能或空间的哈希表，生成这种专门的实现可能不值得。
 *
 *	  与 dynahash 相比，simplehash 具有以下优点：
 *
 *	  - 由于“模板化”代码生成具有已知的结构大小，没有
 *	    间接函数调用（在 dynahash 的配置文件中表现得很明显）。这些特性显著提高了小
 *	    项目的速度。
 *	  - 开放地址在 CPU 缓存行为上优于 dynahash 的链式哈希表。
 *	  - 生成的接口是类型安全的，比 dynahash 更易于使用，
 *	    尽管代价是更复杂的设置。
 *	  - 在 MemoryContext 或其他分配器中以 malloc/free 风格分配内存
 *	    （在共享内存上下文中不易使用）
 *	  - 不需要单独内存上下文的开销。
 *
 * 使用说明：
 *
 *	  要为用例生成哈希表和相关函数，必须在包含此文件之前定义几个
 *	  宏。 包含该文件会取消定义所有这些内容，因此可以在之后生成新的哈希表。
 *	  相关参数有：
 *	  - SH_PREFIX - 所有生成的符号名称的前缀。前缀为 'foo'
 *		将导致哈希表类型为 'foo_hash' 和函数如
 *		'foo_insert'/'foo_lookup' 等等。
 *	  - SH_ELEMENT_TYPE - 包含元素的类型
 *	  - SH_KEY_TYPE - 哈希表的键类型
 *	  - SH_DECLARE - 如果定义，则生成函数原型和类型声明
 *	  - SH_DEFINE - 如果定义，则生成函数定义
 *	  - SH_SCOPE - 函数声明所在的作用域（例如 extern, static inline）
 *	  - SH_RAW_ALLOCATOR - 如果定义，则不使用内存上下文；而是，
 *	    使用此来分配字节。分配器必须将返回的空间置零。
 *	  - SH_USE_NONDEFAULT_ALLOCATOR - 如果定义，则没有元素分配器函数
 *		被定义，因此您可以提供自己的
 *	  以下参数仅在定义 SH_DEFINE 时相关：
 *	  - SH_KEY - 包含哈希键的 SH_ELEMENT_TYPE 中的元素名称
 *	  - SH_EQUAL(table, a, b) - 比较两个表键
 *	  - SH_HASH_KEY(table, key) - 为键生成哈希
 *	  - SH_STORE_HASH - 如果定义，则哈希存储在元素中
 *	  - SH_GET_HASH(tb, a) - 返回存储哈希的字段
 *
 *	  元素类型要求包含一个可以存储 SH_STATUS 枚举中定义的值
 *	  范围的“状态”成员。
 *
 *	  虽然 SH_STORE_HASH（及其后续的 SH_GET_HASH）是可选的，因为
 *	  哈希表实现需要比较哈希以移动元素
 *	  （特别是在扩展哈希时），如果可能，最好将元素的哈希存储
 *	  在元素的数据类型中。如果哈希被这样存储，哈希表在
 *	  比较两个键时也会在调用 SH_EQUAL 之前比较哈希。
 *
 *	  为方便起见，哈希表创建函数接受一个将存储在哈希表类型的
 *	  private_data 成员中的 void 指针。这允许回调引用调用者提供的数据。
 *
 *	  有关用法的示例，请查看 tidbitmap.c（文件本地定义）和
 *	  execnodes.h/execGrouping.c（公开声明，文件本地实现）。
 *
 * 哈希表设计：
 *
 *	  选择的哈希表设计是线性开放地址的一种变体。这样做的原因是
 *	  线性寻址对 CPU 缓存和管道友好。简单线性寻址方案的最大缺点
 *	  是由于聚集导致的查找时间高度可变，以及删除
 *	  留下大量的墓碑。为了解决这些问题，采用了一种“罗宾汉”哈希的变体。
 *	  罗宾汉哈希通过将元素移出逼近其最佳桶的“富”
 *	  元素的方式来优化链长，如果要插入的元素距离其最佳位置更远
 *	  （即，它是“贫穷的”）。虽然这可能会使插入变得更慢，但平均
 *	  查找性能要好得多，并且更高的填充因子可以以仍然有效的方式使用。
 *	  为了避免墓碑 - 通常解决了已删除节点的存在对此决定查找是否
 *	  还需要继续查找或已完成 - 跟随已删除元素的桶将向后移动，
 *	  除非它们为空或已在其最佳位置。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/lib/simplehash.h
 */

#include "port/pg_bitutils.h"

/* helpers */
#define SH_MAKE_PREFIX(a) CppConcat(a,_)
#define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name)
#define SH_MAKE_NAME_(a,b) CppConcat(a,b)

/* 名称宏用于： */

/* 类型声明 */
#define SH_TYPE SH_MAKE_NAME(hash)
#define SH_STATUS SH_MAKE_NAME(status)
#define SH_STATUS_EMPTY SH_MAKE_NAME(SH_EMPTY)
#define SH_STATUS_IN_USE SH_MAKE_NAME(SH_IN_USE)
#define SH_ITERATOR SH_MAKE_NAME(iterator)

/* 函数声明 */
#define SH_CREATE SH_MAKE_NAME(create)
#define SH_DESTROY SH_MAKE_NAME(destroy)
#define SH_RESET SH_MAKE_NAME(reset)
#define SH_INSERT SH_MAKE_NAME(insert)
#define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
#define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
#define SH_DELETE SH_MAKE_NAME(delete)
#define SH_LOOKUP SH_MAKE_NAME(lookup)
#define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
#define SH_GROW SH_MAKE_NAME(grow)
#define SH_START_ITERATE SH_MAKE_NAME(start_iterate)
#define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at)
#define SH_ITERATE SH_MAKE_NAME(iterate)
#define SH_ALLOCATE SH_MAKE_NAME(allocate)
#define SH_FREE SH_MAKE_NAME(free)
#define SH_STAT SH_MAKE_NAME(stat)

/* 内部辅助函数（没有外部可见的原型） */
#define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters)
#define SH_NEXT SH_MAKE_NAME(next)
#define SH_PREV SH_MAKE_NAME(prev)
#define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
#define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
#define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
#define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
#define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)

/* 生成使用哈希表所需的前向声明 */
#ifdef SH_DECLARE

/* 类型定义 */
typedef struct SH_TYPE
{
	/*
	 * 数据/桶数组的大小，64位以处理 UINT32_MAX 大小的哈希
	 * 表。请注意，元素的最大数量较低
	 * （SH_MAX_FILLFACTOR）
	 */
	uint64		size;

	/* 有多少元素具有有效内容 */
	uint32		members;

	/* 基于大小的桶和大小计算的掩码 */
	uint32		sizemask;

	/* 扩展哈希表的边界 */
	uint32		grow_threshold;

	/* 哈希桶 */
	SH_ELEMENT_TYPE *data;

#ifndef SH_RAW_ALLOCATOR
	/* 用于分配的内存上下文 */
	MemoryContext ctx;
#endif

	/* 用户定义的数据，对于回调很有用 */
	void	   *private_data;
}			SH_TYPE;

typedef enum SH_STATUS
{
	SH_STATUS_EMPTY = 0x00,
	SH_STATUS_IN_USE = 0x01
} SH_STATUS;

typedef struct SH_ITERATOR
{
	uint32		cur;			/* 当前元素 */
	uint32		end;
	bool		done;			/* 迭代器耗尽？ */
}			SH_ITERATOR;

/* 外部可见的函数原型 */
#ifdef SH_RAW_ALLOCATOR
/* <prefix>_hash <prefix>_create(uint32 nelements, void *private_data) */
SH_SCOPE	SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
#else
/*
 * <prefix>_hash <prefix>_create(MemoryContext ctx, uint32 nelements,
 *								 void *private_data)
 */
SH_SCOPE	SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
							   void *private_data);
#endif

/* void <prefix>_destroy(<prefix>_hash *tb) */
SH_SCOPE void SH_DESTROY(SH_TYPE * tb);

/* void <prefix>_reset(<prefix>_hash *tb) */
SH_SCOPE void SH_RESET(SH_TYPE * tb);

/* void <prefix>_grow(<prefix>_hash *tb, uint64 newsize) */
SH_SCOPE void SH_GROW(SH_TYPE * tb, uint64 newsize);

/* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);

/*
 * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
 * 								  bool *found)
 */
SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
											uint32 hash, bool *found);

/* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);

/* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
											uint32 hash);

/* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);

/* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);

/* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);

/*
 * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
 *								  uint32 at)
 */
SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);

/* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
SH_SCOPE	SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);

/* void <prefix>_stat(<prefix>_hash *tb */
SH_SCOPE void SH_STAT(SH_TYPE * tb);

#endif							/* SH_DECLARE */


/* 生成哈希表的实现 */
#ifdef SH_DEFINE

#ifndef SH_RAW_ALLOCATOR
#include "utils/memutils.h"
#endif

/* 最大数据数组大小，我们允许最多 PG_UINT32_MAX 个桶，包括 0 */
#define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)

/* 正常填充因子，除非已经接近最大值 */
#ifndef SH_FILLFACTOR
#define SH_FILLFACTOR (0.9)
#endif
/* 如果我们可能出现错误，则增加填充因子 */
#define SH_MAX_FILLFACTOR (0.98)
/* 当实际位置和最优位置大时进行扩展 */
#ifndef SH_GROW_MAX_DIB
#define SH_GROW_MAX_DIB 25
#endif
/* 在插入时，如果需要移动的元素超过，进行扩展 */
#ifndef SH_GROW_MAX_MOVE
#define SH_GROW_MAX_MOVE 150
#endif
#ifndef SH_GROW_MIN_FILLFACTOR
/* 但如果低于 SH_GROW_MAX_* 则不进行扩展 */
#define SH_GROW_MIN_FILLFACTOR 0.1
#endif

#ifdef SH_STORE_HASH
#define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
#else
#define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
#endif

/*
 * 将以下定义包装在包含保护中，以避免如果该头文件被多次包含时出现多重定义错误。
 * 文件的其余部分故意没有包含保护，因为它可以与不同的参数一起包含，以定义具有不冲突名称的函数和类型。
 */
#ifndef SIMPLEHASH_H
#define SIMPLEHASH_H

#ifdef FRONTEND
#define sh_error(...) pg_fatal(__VA_ARGS__)
#define sh_log(...) pg_log_info(__VA_ARGS__)
#else
#define sh_error(...) elog(ERROR, __VA_ARGS__)
#define sh_log(...) elog(LOG, __VA_ARGS__)
#endif

#endif

/*
 * 计算哈希表的大小参数。在创建和扩展哈希表时调用。
 */
static inline void
SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint64 newsize)
{
	uint64		size;

	/* 支持零大小的哈希会使事情变得复杂 */
	size = Max(newsize, 2);

	/* 将大小向上舍入到下一个 2 的幂，这就是桶的工作方式 */
	size = pg_nextpower2_64(size);
	Assert(size <= SH_MAX_SIZE);

	/*
	 * 验证在该平台上分配 ->data 是否可能，而不会溢出 Size。
	 */
	if (unlikely((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2))
		sh_error("hash table too large");

	/* 现在设置大小 */
	tb->size = size;
	tb->sizemask = (uint32) (size - 1);

	/*
	 * 计算需要再次扩展哈希表的下一个阈值。
	 */
	if (tb->size == SH_MAX_SIZE)
		tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
	else
		tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
}

/* 返回该哈希的最优桶 */
static inline uint32
SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
{
	return hash & tb->sizemask;
}

/* 返回当前桶之后的下一个桶，处理环绕 */
static inline uint32
SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
{
	curelem = (curelem + 1) & tb->sizemask;

	Assert(curelem != startelem);

	return curelem;
}

/* 返回当前桶之前的桶，处理环绕 */
static inline uint32
SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
{
	curelem = (curelem - 1) & tb->sizemask;

	Assert(curelem != startelem);

	return curelem;
}

/* 返回桶与其最优位置之间的距离 */
static inline uint32
SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
{
	if (optimal <= bucket)
		return bucket - optimal;
	else
		return (tb->size + bucket) - optimal;
}

static inline uint32
SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
{
#ifdef SH_STORE_HASH
	return SH_GET_HASH(tb, entry);
#else
	return SH_HASH_KEY(tb, entry->SH_KEY);
#endif
}

/* 默认内存分配函数 */
static inline void *SH_ALLOCATE(SH_TYPE * type, Size size);
static inline void SH_FREE(SH_TYPE * type, void *pointer);

#ifndef SH_USE_NONDEFAULT_ALLOCATOR

/* 默认内存分配函数 */
static inline void *
SH_ALLOCATE(SH_TYPE * type, Size size)
{
#ifdef SH_RAW_ALLOCATOR
	return SH_RAW_ALLOCATOR(size);
#else
	return MemoryContextAllocExtended(type->ctx, size,
									  MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
#endif
}

/* 默认内存释放函数 */
static inline void
SH_FREE(SH_TYPE * type, void *pointer)
{
	pfree(pointer);
}

#endif

/*
 * 创建一个哈希表，足够存放 `nelements` 个不同的成员。
 * 哈希表的内存从传入的上下文中分配。如果需要，元素数组可以使用传入的分配器进行分配；
 * 这样做可能有助于将元素数组放置在共享内存中，或者放在一个会比哈希表其余部分更长久的上下文中。
 * 除了元素数组的内存外，其余内存仍将从传入的上下文中分配。
 */
#ifdef SH_RAW_ALLOCATOR
SH_SCOPE	SH_TYPE *
SH_CREATE(uint32 nelements, void *private_data)
#else
SH_SCOPE	SH_TYPE *
SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
#endif
{
	SH_TYPE    *tb;
	uint64		size;

#ifdef SH_RAW_ALLOCATOR
	tb = (SH_TYPE *) SH_RAW_ALLOCATOR(sizeof(SH_TYPE));
#else
	tb = (SH_TYPE *) MemoryContextAllocZero(ctx, sizeof(SH_TYPE));
	tb->ctx = ctx;
#endif
	tb->private_data = private_data;

	/* 增加 nelements 以填充因子，想要存储 nelements 个元素 */
	size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR);

	SH_COMPUTE_PARAMETERS(tb, size);

	tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size);

	return tb;
}

/* 销毁一个先前创建的哈希表 */
SH_SCOPE void
SH_DESTROY(SH_TYPE * tb)
{
	SH_FREE(tb, tb->data);
	pfree(tb);
}

/* 重置一个先前创建的哈希表的内容 */
SH_SCOPE void
SH_RESET(SH_TYPE * tb)
{
	memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
	tb->members = 0;
}

/*
 * 将哈希表扩展到至少 `newsize` 个桶。
 *
 * 通常，当有必要时，这会在插入/删除时自动调用。但在某些情况下，调整大小到精确的输入大小在性能上可能是有优势的。
 */
SH_SCOPE void
SH_GROW(SH_TYPE * tb, uint64 newsize)
{
	uint64		oldsize = tb->size;
	SH_ELEMENT_TYPE *olddata = tb->data;
	SH_ELEMENT_TYPE *newdata;
	uint32		i;
	uint32		startelem = 0;
	uint32		copyelem;

	Assert(oldsize == pg_nextpower2_64(oldsize));
	Assert(oldsize != SH_MAX_SIZE);
	Assert(oldsize < newsize);

	/* 计算新表的参数 */
	SH_COMPUTE_PARAMETERS(tb, newsize);

	tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size);

	newdata = tb->data;

	/*
	 * 从旧数据复制条目到新数据。理论上我们可以在这里使用 SH_INSERT，以避免代码重复，但那比我们需要的更通用。
	 * 我们既不希望 tb->members 增加，也不需要处理已删除的元素，也不需要比较键。
	 * 因此，特定案例的实现要快得多。由于调整大小可能耗时且频繁，因此值得优化。
	 *
	 * 为了能够简单地移动条目，我们必须从不是第一个桶开始（即 olddata[0]），
	 * 而是找到第一个桶，它要么是空的，要么是由其最优位置的条目占用的。
	 * 这样的桶在负载因子低于 1 的任何表中必须存在，因为并非所有桶都是占用的，
	 * 即总是需要有一个空桶。通过从这样的桶开始，我们可以将条目移动到更大的表中，
	 * 而无需处理冲突。
	 */

	/* 搜索哈希中第一个不是环绕的元素 */
	for (i = 0; i < oldsize; i++)
	{
		SH_ELEMENT_TYPE *oldentry = &olddata[i];
		uint32		hash;
		uint32		optimal;

		if (oldentry->status != SH_STATUS_IN_USE)
		{
			startelem = i;
			break;
		}

		hash = SH_ENTRY_HASH(tb, oldentry);
		optimal = SH_INITIAL_BUCKET(tb, hash);

		if (optimal == i)
		{
			startelem = i;
			break;
		}
	}

	/* 并复制旧表中的所有元素 */
	copyelem = startelem;
	for (i = 0; i < oldsize; i++)
	{
		SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];

		if (oldentry->status == SH_STATUS_IN_USE)
		{
			uint32		hash;
			uint32		startelem;
			uint32		curelem;
			SH_ELEMENT_TYPE *newentry;

			hash = SH_ENTRY_HASH(tb, oldentry);
			startelem = SH_INITIAL_BUCKET(tb, hash);
			curelem = startelem;

			/* 找到空元素以放入数据 */
			while (true)
			{
				newentry = &newdata[curelem];

				if (newentry->status == SH_STATUS_EMPTY)
				{
					break;
				}

				curelem = SH_NEXT(tb, curelem, startelem);
			}

			/* 将条目复制到新插槽 */
			memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE));
		}

		/* 这里不能使用 SH_NEXT，应该使用新大小 */
		copyelem++;
		if (copyelem >= oldsize)
		{
			copyelem = 0;
		}
	}

	SH_FREE(tb, olddata);
}

/*
 * 这是一个独立的静态内联函数，因此它可以可靠地内联
 * 到其包装函数中，即使 SH_SCOPE 是 extern。
 */
static inline SH_ELEMENT_TYPE *
SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
{
	uint32		startelem;
	uint32		curelem;
	SH_ELEMENT_TYPE *data;
	uint32		insertdist;

restart:
	insertdist = 0;

	/*
	 * 我们即使在键实际上存在时也进行扩展检查，以避免
	 * 在循环内部进行检查。这也让我们避免在调整大小后
	 * 重新找到在哈希表中的位置。
	 *
	 * 请注意，在由于 SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE 而调整大小时
	 * 也会到达此处。
	 */
	if (unlikely(tb->members >= tb->grow_threshold))
	{
		if (unlikely(tb->size == SH_MAX_SIZE))
			sh_error("hash table size exceeded");

		/*
		 * 在优化时，打印这些信息非常有用。
		 */
		/* SH_STAT(tb); */
		SH_GROW(tb, tb->size * 2);
		/* SH_STAT(tb); */
	}

	/* 执行插入，从最佳位置开始桶搜索 */
	data = tb->data;
	startelem = SH_INITIAL_BUCKET(tb, hash);
	curelem = startelem;
	while (true)
	{
		uint32		curdist;
		uint32		curhash;
		uint32		curoptimal;
		SH_ELEMENT_TYPE *entry = &data[curelem];

		/* 任何空桶都可以直接使用 */
		if (entry->status == SH_STATUS_EMPTY)
		{
			tb->members++;
			entry->SH_KEY = key;
#ifdef SH_STORE_HASH
			SH_GET_HASH(tb, entry) = hash;
#endif
			entry->status = SH_STATUS_IN_USE;
			*found = false;
			return entry;
		}

		/*
		 * 如果桶不为空，我们要么找到了匹配（在这种情况下
		 * 结束），要么必须决定是跳过还是移动冲突条目。当冲突元素距离其
		 * 最佳位置的距离小于要插入条目的距离时，我们
		 * 将冲突条目（及其后续项）向前移动一个位置。
		 */

		if (SH_COMPARE_KEYS(tb, hash, key, entry))
		{
			Assert(entry->status == SH_STATUS_IN_USE);
			*found = true;
			return entry;
		}

		curhash = SH_ENTRY_HASH(tb, entry);
		curoptimal = SH_INITIAL_BUCKET(tb, curhash);
		curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);

		if (insertdist > curdist)
		{
			SH_ELEMENT_TYPE *lastentry = entry;
			uint32		emptyelem = curelem;
			uint32		moveelem;
			int32		emptydist = 0;

			/* 查找下一个空桶 */
			while (true)
			{
				SH_ELEMENT_TYPE *emptyentry;

				emptyelem = SH_NEXT(tb, emptyelem, startelem);
				emptyentry = &data[emptyelem];

				if (emptyentry->status == SH_STATUS_EMPTY)
				{
					lastentry = emptyentry;
					break;
				}

				/*
				 * 为了避免因过度不平衡的哈希表带来的负面后果，
				 * 如果冲突导致我们需要移动大量条目，则增加哈希表的大小。
				 * 这种不平衡最有可能的原因是，从一个
				 * 当前较大的哈希表以哈希表顺序填充一个
				 * 当前较小的表。不增加哈希表的大小如果
				 * 它太空，以防止一些奇怪边缘情况快速空间
				 * 爆炸。
				 */
				if (unlikely(++emptydist > SH_GROW_MAX_MOVE) &&
					((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
				{
					tb->grow_threshold = 0;
					goto restart;
				}
			}

			/* 向前移动，从最后一个占用元素开始 */

			/*
			 * TODO: 这在很多情况下可以优化为一个 memcpy，
			 * 除非在 ->data 的末尾环绕。不过到目前为止，
			 * 这在分析中还没有出现。
			 */
			moveelem = emptyelem;
			while (moveelem != curelem)
			{
				SH_ELEMENT_TYPE *moveentry;

				moveelem = SH_PREV(tb, moveelem, startelem);
				moveentry = &data[moveelem];

				memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE));
				lastentry = moveentry;
			}

			/* 并填充现在的空位 */
			tb->members++;

			entry->SH_KEY = key;
#ifdef SH_STORE_HASH
			SH_GET_HASH(tb, entry) = hash;
#endif
			entry->status = SH_STATUS_IN_USE;
			*found = false;
			return entry;
		}

		curelem = SH_NEXT(tb, curelem, startelem);
		insertdist++;

		/*
		 * 为了避免因过度不平衡的哈希表带来的负面后果，
		 * 如果冲突导致大型运行，则增加哈希表的大小。
		 * 这种不平衡最有可能的原因是，从一个
		 * 当前较大的哈希表以哈希表顺序填充一个
		 * 当前较小的表。不增加哈希表的大小如果
		 * 它太空，以防止一些奇怪边缘情况快速空间
		 * 爆炸。
		 */
		if (unlikely(insertdist > SH_GROW_MAX_DIB) &&
			((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
		{
			tb->grow_threshold = 0;
			goto restart;
		}
	}
}

/*
 * 将键 key 插入哈希表，如果键已存在则将 *found 设置为 true，
 * 否则为 false。无论哪种情况，返回哈希表条目。
 */
SH_SCOPE	SH_ELEMENT_TYPE *
SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
{
	uint32		hash = SH_HASH_KEY(tb, key);

	return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
}

/*
 * 使用已计算的哈希将键 key 插入哈希表。
 * 如果键已存在则将 *found 设置为 true，false
 * 否则。无论哪种情况，返回哈希表条目。
 */
SH_SCOPE	SH_ELEMENT_TYPE *
SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
{
	return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
}

/*
 * 这是一个独立的静态内联函数，因此它可以可靠地内联
 * 到其包装函数中，即使 SH_SCOPE 是 extern。
 */
static inline SH_ELEMENT_TYPE *
SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
{
	const uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
	uint32		curelem = startelem;

	while (true)
	{
		SH_ELEMENT_TYPE *entry = &tb->data[curelem];

		if (entry->status == SH_STATUS_EMPTY)
		{
			return NULL;
		}

		Assert(entry->status == SH_STATUS_IN_USE);

		if (SH_COMPARE_KEYS(tb, hash, key, entry))
			return entry;

		/*
		 * TODO: 我们可以基于距离停止搜索。如果当前
		 * 桶的距离-最佳小于我们已跳过的内容，条目不存在。
		 * 可能只有在定义了 SH_STORE_HASH 时这样做，以避免重新计算哈希？
		 */

		curelem = SH_NEXT(tb, curelem, startelem);
	}
}

/*
 * 在哈希表中查找条目。如果键不存在，则返回 NULL。
 */
SH_SCOPE	SH_ELEMENT_TYPE *
SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key)
{
	uint32		hash = SH_HASH_KEY(tb, key);

	return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
}

/*
 * 使用已计算的哈希在哈希表中查找条目。
 *
 * 如果键不存在，则返回 NULL。
 */
SH_SCOPE	SH_ELEMENT_TYPE *
SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
{
	return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
}

/*
 * 通过键从哈希表中删除条目。返回要删除的键是否存在。
 */
SH_SCOPE bool
SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
{
	uint32		hash = SH_HASH_KEY(tb, key);
	uint32		startelem = SH_INITIAL_BUCKET(tb, hash);
	uint32		curelem = startelem;

	while (true)
	{
		SH_ELEMENT_TYPE *entry = &tb->data[curelem];

		if (entry->status == SH_STATUS_EMPTY)
			return false;

		if (entry->status == SH_STATUS_IN_USE &&
			SH_COMPARE_KEYS(tb, hash, key, entry))
		{
			SH_ELEMENT_TYPE *lastentry = entry;

			tb->members--;

			/*
			 * 向后移动后续元素，直到遇到空元素
			 * 或者元素处于其最佳位置。
			 *
			 * 尽管这听起来开销很大，但平均链的长度很短，
			 * 而删除否则将需要墓碑。
			 */
			while (true)
			{
				SH_ELEMENT_TYPE *curentry;
				uint32		curhash;
				uint32		curoptimal;

				curelem = SH_NEXT(tb, curelem, startelem);
				curentry = &tb->data[curelem];

				if (curentry->status != SH_STATUS_IN_USE)
				{
					lastentry->status = SH_STATUS_EMPTY;
					break;
				}

				curhash = SH_ENTRY_HASH(tb, curentry);
				curoptimal = SH_INITIAL_BUCKET(tb, curhash);

				/* 当前处于最佳位置，完成 */
				if (curoptimal == curelem)
				{
					lastentry->status = SH_STATUS_EMPTY;
					break;
				}

				/* shift */
				memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));

				lastentry = curentry;
			}

			return true;
		}

		/* TODO: 如果距离太大，返回 false */

		curelem = SH_NEXT(tb, curelem, startelem);
	}
}

/*
 * 通过条目指针从哈希表中删除条目
 */
SH_SCOPE void
SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
{
	SH_ELEMENT_TYPE *lastentry = entry;
	uint32		hash = SH_ENTRY_HASH(tb, entry);
	uint32		startelem = SH_INITIAL_BUCKET(tb, hash);
	uint32		curelem;

	/* 计算 'entry' 的索引 */
	curelem = entry - &tb->data[0];

	tb->members--;

	/*
	 * 向后移动后续元素，直到遇到空元素或
	 * 元素处于其最佳位置。
	 *
	 * 尽管这听起来开销很大，但平均链的长度很短，且
	 * 删除否则将需要墓碑。
	 */
	while (true)
	{
		SH_ELEMENT_TYPE *curentry;
		uint32		curhash;
		uint32		curoptimal;

		curelem = SH_NEXT(tb, curelem, startelem);
		curentry = &tb->data[curelem];

		if (curentry->status != SH_STATUS_IN_USE)
		{
			lastentry->status = SH_STATUS_EMPTY;
			break;
		}

		curhash = SH_ENTRY_HASH(tb, curentry);
		curoptimal = SH_INITIAL_BUCKET(tb, curhash);

		/* 当前处于最佳位置，完成 */
		if (curoptimal == curelem)
		{
			lastentry->status = SH_STATUS_EMPTY;
			break;
		}

		/* shift */
		memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));

		lastentry = curentry;
	}
}

/*
 * 初始化迭代器。
 */
SH_SCOPE void
SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
{
	uint64		startelem = PG_UINT64_MAX;

	/*
	 * 搜索第一个空元素。由于在迭代期间支持删除，
	 * 我们希望从一个无法受到
	 * 元素移动影响的元素开始/结束。
	 */
	for (uint32 i = 0; i < tb->size; i++)
	{
		SH_ELEMENT_TYPE *entry = &tb->data[i];

		if (entry->status != SH_STATUS_IN_USE)
		{
			startelem = i;
			break;
		}
	}

	/* 我们应该找到一个空元素 */
	Assert(startelem < SH_MAX_SIZE);

	/*
	 * 反向迭代，这样允许当前元素被删除，即使有向后移动
	 */
	iter->cur = startelem;
	iter->end = iter->cur;
	iter->done = false;
}

/*
 * 初始化迭代器到特定的桶。这实际上仅在调用者部分迭代哈希空间时有用，而这种迭代根据访问的条目删除和插入元素。重复这样做可能导致键空间不平衡，因为总是从同一位置开始。
 */
SH_SCOPE void
SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at)
{
	/*
	 * 反向迭代，这样允许当前元素被删除，即使有向后移动。
	 */
	iter->cur = at & tb->sizemask;	/* 确保 at 在有效范围内 */
	iter->end = iter->cur;
	iter->done = false;
}

/*
 * 遍历哈希表中的所有条目。返回下一个被占用的条目，
 * 如果完成则返回 NULL。
 *
 * 在迭代过程中，哈希表中的当前条目可以被删除，
 * 而不会导致元素被跳过或被返回两次。此外
 * 表中的其余部分可能被修改（即可以有插入或
 * 删除），但如果这样做，既不能保证所有节点至少被访问一次，也不能保证某个节点最多被访问一次。
 */
SH_SCOPE	SH_ELEMENT_TYPE *
SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
{
	while (!iter->done)
	{
		SH_ELEMENT_TYPE *elem;

		elem = &tb->data[iter->cur];

		/* 向后方向的下一个元素 */
		iter->cur = (iter->cur - 1) & tb->sizemask;

		if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
			iter->done = true;
		if (elem->status == SH_STATUS_IN_USE)
		{
			return elem;
		}
	}

	return NULL;
}

/*
 * 报告有关哈希表状态的一些统计信息。仅用于
 * 调试/性能分析目的。
 */
SH_SCOPE void
SH_STAT(SH_TYPE * tb)
{
	uint32		max_chain_length = 0;
	uint32		total_chain_length = 0;
	double		avg_chain_length;
	double		fillfactor;
	uint32		i;

	uint32	   *collisions = (uint32 *) palloc0(tb->size * sizeof(uint32));
	uint32		total_collisions = 0;
	uint32		max_collisions = 0;
	double		avg_collisions;

	for (i = 0; i < tb->size; i++)
	{
		uint32		hash;
		uint32		optimal;
		uint32		dist;
		SH_ELEMENT_TYPE *elem;

		elem = &tb->data[i];

		if (elem->status != SH_STATUS_IN_USE)
			continue;

		hash = SH_ENTRY_HASH(tb, elem);
		optimal = SH_INITIAL_BUCKET(tb, hash);
		dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i);

		if (dist > max_chain_length)
			max_chain_length = dist;
		total_chain_length += dist;

		collisions[optimal]++;
	}

	for (i = 0; i < tb->size; i++)
	{
		uint32		curcoll = collisions[i];

		if (curcoll == 0)
			continue;

		/* 单一包含元素不是冲突 */
		curcoll--;
		total_collisions += curcoll;
		if (curcoll > max_collisions)
			max_collisions = curcoll;
	}

	/* 足够大以值得释放，即使仅用于调试 */
	pfree(collisions);

	if (tb->members > 0)
	{
		fillfactor = tb->members / ((double) tb->size);
		avg_chain_length = ((double) total_chain_length) / tb->members;
		avg_collisions = ((double) total_collisions) / tb->members;
	}
	else
	{
		fillfactor = 0;
		avg_chain_length = 0;
		avg_collisions = 0;
	}

	sh_log("size: " UINT64_FORMAT ", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %u, avg_collisions: %f",
		   tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length,
		   total_collisions, max_collisions, avg_collisions);
}

#endif							/* SH_DEFINE */


/* 未定义外部参数，以便下一个哈希表可以被定义 */
#undef SH_PREFIX
#undef SH_KEY_TYPE
#undef SH_KEY
#undef SH_ELEMENT_TYPE
#undef SH_HASH_KEY
#undef SH_SCOPE
#undef SH_DECLARE
#undef SH_DEFINE
#undef SH_GET_HASH
#undef SH_STORE_HASH
#undef SH_USE_NONDEFAULT_ALLOCATOR
#undef SH_EQUAL

/* 未定义局部声明的宏 */
#undef SH_MAKE_PREFIX
#undef SH_MAKE_NAME
#undef SH_MAKE_NAME_
#undef SH_FILLFACTOR
#undef SH_MAX_FILLFACTOR
#undef SH_GROW_MAX_DIB
#undef SH_GROW_MAX_MOVE
#undef SH_GROW_MIN_FILLFACTOR
#undef SH_MAX_SIZE

/* types */
#undef SH_TYPE
#undef SH_STATUS
#undef SH_STATUS_EMPTY
#undef SH_STATUS_IN_USE
#undef SH_ITERATOR

/* 外部函数名称 */
#undef SH_CREATE
#undef SH_DESTROY
#undef SH_RESET
#undef SH_INSERT
#undef SH_INSERT_HASH
#undef SH_DELETE_ITEM
#undef SH_DELETE
#undef SH_LOOKUP
#undef SH_LOOKUP_HASH
#undef SH_GROW
#undef SH_START_ITERATE
#undef SH_START_ITERATE_AT
#undef SH_ITERATE
#undef SH_ALLOCATE
#undef SH_FREE
#undef SH_STAT

/* 内部函数名称 */
#undef SH_COMPUTE_PARAMETERS
#undef SH_COMPARE_KEYS
#undef SH_INITIAL_BUCKET
#undef SH_NEXT
#undef SH_PREV
#undef SH_DISTANCE_FROM_OPTIMAL
#undef SH_ENTRY_HASH
#undef SH_INSERT_HASH_INTERNAL
#undef SH_LOOKUP_HASH_INTERNAL
